The present invention relates to a sequential decoder and a receiver using a sequential decoder, and more particularly to a sequential decoder which can be applied to broadband mobile communications and reduces the computational efforts of a sequence estimation, and a receiver equipped with the same.
There are a block code and a convolutional code as error correction codes. There are Viterbi decoding and sequential decoding as decoding of the convolutional code. The Viterbi decoding is a method of decoding which utilizes a repetition structure of the convolutional code and efficiently performs maximum likelihood decoding. The sequential decoding utilizes a tree structure and approximately performs maximum likelihood decoding with a given memory capacity and a limited number of computations.
However, the Viterbi decoding handles equal-length paths at each time, while the sequential decoding handles a variable-length path. Thus, the sequential decoding does not use a metric used in the Viterbi decoding. For example, although the Hamming distance in a binary symmetric channel takes a metric of the Viterbi decoding, it is not suitable for a case where paths having different lengths are objects to be compared. That is, the Hamming distance of even the maximum likelihood path from a received sequence increases as it becomes longer, and thus the maximum likelihood path has a metric greater than any paths shorter than the same.
Thus, let us consider the following branch metric xcexc(yt,wt) with respect to a q-ary convolutional code (code rate k/n) in which the length of the information block is k and the length of the encoded block is n:                               μ          ⁢                      xe2x80x83                    ⁢                      (                                          y                t                            ,                              w                t                                      )                          =                                            -              log                        ⁢                          xe2x80x83                        ⁢                                          P                ⁡                                  (                                                            y                      t                                        ⁢                                          ❘                                        ⁢                                          w                      t                                                        )                                                            P                ⁡                                  (                                      y                    t                                    )                                                              +                      k            ⁢                          xe2x80x83                        ⁢            log            ⁢                          xe2x80x83                        ⁢            q                                              (        1        )            
where yt and wt respectively denote a received block and encoded block (a branch in the trellis diagram) at time t. Also, P(yt) denotes a probability that the received block at time t is yt. Further, P(yt|wt) denotes a conditional probability that the received block at time t is yi when the encoded block at time t is wt.
A metric between a received sequence YL=y0y1y2 . . . yLxe2x88x921 and an encoded sequence (path) WL=w0w1w2w3 . . . wLxe2x88x921 is defined by the following equation:                               μ          ⁢                      xe2x80x83                    ⁢                      (                                          y                L                            ,                              w                L                                      )                          =                              ∑                          i              =              0                                      L              -              1                                ⁢                      μ            ⁢                          xe2x80x83                        ⁢                          (                                                y                  t                                ,                                  w                  t                                            )                                                          (        2        )            
It is assumed that the communication channel is a memoryless, stationary channel. The metric thus defined above is called a Fano metric (sometimes, an expression obtained by multiplying equation (2) by xe2x88x921 is defined as the Fano metric).
When an information sequence is random, in the normal convolutional code, all patterns of a length n appear in the code block at each time with an equal probability except for a few times in the commencement of encoding. Now, it is further assumed that the communication channel is a q-ary symmetric communication channel. In this case, all patterns of length n appear in each block of the received sequence except for a few times in the commencement. Thus, P(yi)=qxe2x88x92n. By substituting this into equation (1), the following is obtained:
xcexc(yt,wt)=P(yt|wt)xe2x88x92(nxe2x88x92k)log qxe2x80x83xe2x80x83(3)
The first term of equation (3) is no more than the branch metric in the Viterbi decoding. Thus, the Fano metric is biased with xe2x88x92(nxe2x88x92k)log q which is not involved in the branch metric of the Viterbi decoding. The metric of the maximum likelihood does not increase even if it is longer, and does not have any disadvantage as compared to short paths.
A description will now be given of computation of the Fano metric in the sequential decoding by exemplarily describing a case where the sequential decoding is applied to a sequence estimation in mobile communications. A feature of mobile communications is that the radio propagation environment is a multipath propagation. When considering an up (transmission from a mobile station, reception in a base station) communication channel, a bundle of transmitted element waves which have been subject to scatter, diffraction and reflection around the mobile station arrives at the base station directly or after it is reflected at a great distance. Hence, the base station receives the transmitted signal in such a fashion that a plurality of components resulting from the transmitted signal have different incoming angles. These respective paths are subject to independent fading.
When a communication takes place in the mobile communication environment as described above, phenomena different from each other due to the bandwidths of the signals appear in the received signals. In a case where the transmitted signal has a low bit rate and the bandwidth thereof is much narrower than a coherence bandwidth in the channel, the differences in propagation delay time among the signals propagated through the above-mentioned paths are much smaller than the symbol time length (which is normally equal to the reciprocal number of the symbol rate) of the signals. In this case, the same information symbol is received on the reception side, and a waveform distortion due to intersymbol interference does not occur in the received signals.
When the bit rate of the transmitted signals increases and the bandwidth of the signals becomes approximately equal to the coherence bandwidth in the channel, information symbols different from each other in the respective paths are received. In this case, a waveform distortion due to intersymbol interference over a few past and future symbols occurs in the received signals. Since the paths are subject to the respective, independent fading as has been described above, the intersymbol interference over a few past and future symbols is a time-varying intersymbol interference in which the intersymbol interference varies with time.
Thus, an equalizer which eliminates the intersymbol interference is required to estimate a channel impulse response (which is equivalent to an arrangement in which the complex amplitudes of the paths are arranged in the order of arrival time) and to thus estimate the transmitted sequence. An algorithm based on the maximum likelihood sequence estimation theory (MLSE theory) can be applied to estimation of the transmitted sequence. When the intersymbol interference results from a few past and future symbols, the joint signal processing of channel estimation and MLSE can be achieved with reasonable complexity. This is described in detail in, for example, a literature: Fukawa, Suzuki, xe2x80x9cRecursive Least Squares Adaptive Maximum Likelihood Sequence Estimation (RLS-MLSE)xe2x80x94An Application of Maximum Likelihood Estimation Theory to Mobile Radioxe2x80x9d, The Transaction of the Institute of Electronics, Information and Communication Engineers (B-11), J76-B-II, No. 4, PP. 202-214, April 1993.
As the transmission bit rate increases, the received signal is affected by an increased amount of intersymbol interference. Theoretically, the above-mentioned joint signal processing of the channel estimation and the MLSE can be applied to equalization of the intersymbol interference. However, the number of states in the Viterbi algorithm used in the MLSE increases exponentially with respect to the length of the intersymbol interference (equal to the channel memory length). For example, in a case where binary phase shift keying (BPSK) is used as a modulation method, if there is a channel memory length of 11 symbols, the number of states (involved in a 12-path channel) is 2048, which exceeds the practical complexity limit.
It will be seen from the above consideration, it can be said that technical drawbacks to be solved in order to achieve an adaptive equalizer in high-bit-rate channels on the megabit order are involved in the sequence estimation and channel estimation corresponding to the above sequence. Of the above drawbacks, an adaptive equalizer using a sequential sequence estimation instead of the maximum likelihood sequence estimation MLSE is proposed, as means for avoiding the difficulty in the sequence estimation, in a literature: Matumoto, xe2x80x9cSequential Sequence Estimation and Equalization in High Speed Mobile Communicationsxe2x80x9d, Proceedings of The 1997 Communications Society Conference of IEICE, B-5-149.
Sequential sequence estimation was originally developed as an algorithm for decoding convolutional codes having a long constraint length. More particularly, from a historical point of view, the sequential sequence estimation was directed to developing an application for deep space communication which applies to a constraint length as long as 40 to 60. The process in which the intersymbol interference occurs is no more than convolutional computation on a complex number field. Thus, it is apparent that sequential sequence estimation has affinity with adaptive equalization. The above document shows that a sequential sequence estimation is performed in 12 channels by using the BPSK, and the results of the above estimation show good performance can be obtained by reasonable complexity.
When sequential decoding is applied, as sequential sequence estimation, to mobile communications, the Fano metric can be computed by the following formula (see: F. Xiong, xe2x80x9cSequential Sequence Estimation for Channels with Intersymbol Interference of Finite or Infinite Lengthxe2x80x9d, IEEE Trans. Commun. vol.COM-38, No.6, PP.795-804, 1990):                                           P            0                    ⁡                      (                          z              k                        )                          =                              1                          M              L                                ⁢                      xe2x80x83                    ⁢                                    ∑                              j                =                1                                            M                L                                      ⁢                          xe2x80x83                        ⁢                                          1                                                                            2                      ⁢                                              xe2x80x83                                            ⁢                      π                                                        ⁢                  σ                                            ⁢                              xe2x80x83                            ⁢              exp              ⁢                              xe2x80x83                            ⁢                              {                                  -                                                                                    (                                                                              z                            k                                                    -                                                      y                            j                                                                          )                                            2                                                              2                      ⁢                                              xe2x80x83                                            ⁢                                              σ                        2                                                                                            }                                                                        (        4        )                                                      P            n                    ⁡                      (                                          z                k                            -                              y                k                                      )                          =                  xe2x80x83                ⁢                              1                                                            2                  ⁢                                      xe2x80x83                                    ⁢                  π                                            ⁢              σ                                ⁢                      xe2x80x83                    ⁢          exp          ⁢                      xe2x80x83                    ⁢                      {                          -                                                                    (                                                                  z                        k                                            -                                              y                        k                                                              )                                    2                                                  2                  ⁢                                      xe2x80x83                                    ⁢                                      σ                    2                                                                        }                                              (        5        )                                          λ          ⁢                      xe2x80x83                    ⁢                      (                                          y                k                            ,                              z                k                                      )                          =                              log            ⁢                          xe2x80x83                        ⁢                                                            P                  n                                ⁢                                  xe2x80x83                                ⁢                                  (                                                            z                      k                                        -                                          y                      k                                                        )                                                                              P                  0                                ⁢                                  xe2x80x83                                ⁢                                  (                                      z                    k                                    )                                                              -                      log            ⁢                          xe2x80x83                        ⁢            M                                              (        6        )            
where in equations (4), (5) and (6), M is a modulation multiplicity, L is the constraint number (the channel memory length), "sgr"2 is noise power, zk is the received sample value, yi is a replica of the received signal, and xcex(yk,zk) is the Fano metric.
According to equation (4), in P0(zk) forming the Fano metric xcex(yk,zk), all of items of information (1 to ML for j) which may be transmitted with respect to the constraint length L are added.
Thus, the computational efforts of computation of equation (4) increases exponentially to a very large value as the value of L becomes greater. Thus, it takes a huge amount of time to achieve the computation process.
An object of the present invention is to reduce the computational efforts necessary for obtaining Fano metrics and reduce the time necessary for computation in a sequential decoder and a receiver equipped with such a decoder.
The present invention includes the following means as means for achieving the above object.
In the invention described in claim 1, a sequential decoder which performs decoding using Fano""s likelihood values is characterized in that decoding is performed by referring to a history of a path and computing a likelihood value.
In the invention described in claim 2, the sequential decoder as claimed in claim 1 is characterized in that there is provided a transversal filter which generates a replica of a received signal, a history of a path related to a corresponding signal in modulation constellation applied to a given small tap coefficient of the transversal filter is referred to.
In the invention described in claim 3, the sequential decoder as claimed in claim 2 is characterized in that histories of some paths related to corresponding signals in modulation constellation applied to given small tap coefficients of the transversal filter are referred to in an increasing order of the tap coefficients of the transversal filter.
In the invention described in claim 4, the sequential decoder as claimed in claim 1 is characterized in that histories of consecutive paths which are paths within a constraint length and are the oldest in time are referred to.
In the invention described in claim 5, a sequential decoder which performs decoding using Fano""s likelihood values is characterized in that there is provided a transversal filter which generates a predicted value of a received signal, a path related to a signal phase point signal applied to a given small tap coefficient of the transversal filter is ignored.
In the invention described in claim 6, the sequential decoder as claimed in any of claims 1 to 5 is characterized in that the decoder performs decoding using the Fano""s likelihood values with respect to a signal of a channel which has a constraint length L (L is a natural number equal to or greater than 2) and a modulation multiple-valued number M, and performs the decoding by computing the likelihood values with regard to ML-A paths (A is an integer satisfying 0 less than A less than L).
In the invention described in claim 7, a receiver is equipped with the sequential decoder as claimed in any of claims 1 to 6.
According to the invention described in claims 1 to 6, it is possible to provide a sequential decoder capable of reducing the amount of computation for computing Fano metrics and reducing the time necessary for the computing process.
According to the invention described in claim 7, it is possible to provide a receiver equipped with a sequential decoder capable of reducing the amount of computation for computing Fano metrics and reducing the time necessary for the computing process.